package graph2.component;

import graph2.Graph;
import sun.awt.image.ImageWatched;

import java.util.LinkedList;

/**
 * 采用深度优先遍历的方式进行寻路
 */
public class Path {
    /**
     * 图的引用
     */
    private Graph graph;
    /**
     * 节点是否被遍历过
     */
    private boolean[] visited;
    /**
     * 来自其他节点
     */
    private int[] from;
    /**
     * 原点
     */
    private int src;


    public Path(Graph graph, int src) {
        this.graph = graph;
        from = new int[graph.V()];
        visited = new boolean[graph.V()];

        for (int i = 0; i < graph.V(); i++) {
            from[i] = -1;
        }

        dfs(src);
    }

    /**
     * 深度优先遍历
     *
     * @param i
     */
    private void dfs(int i) {
        visited[i] = true;
        Iterable<Integer> nodes = graph.adj(i);
        for (Integer node : nodes) {
            if (!visited[node]) {
                from[node] = i;
                dfs(node);
            }
        }
    }


    /**
     * 是否有路
     *
     * @return
     */
    public boolean hasPath(int v) {
        return visited[v];
    }

    /**
     * 返回一个点的所有路径
     *
     * @param v
     * @return
     */
    public LinkedList path(int v) {
        LinkedList<Integer> nodes = new LinkedList<>();
        while (from[v] != -1) {
            nodes.addFirst(from[v]);
            v = from[v];
        }
        return nodes;
    }

    /**
     * 打印一个路径
     *
     * @param v
     * @return
     */
    public void showPath(int v) {
        LinkedList path = path(v);
        System.out.println(path + "->" + v);
    }


}
